package priv.conceit.study.leetcode.medium;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

/**
 * 编号94
 * 二叉树的中序遍历
 * <a href="https://leetcode-cn.com/problems/binary-tree-inorder-traversal/"></a>
 * 给定一个二叉树，返回它的 中序 遍历。
 * <p>
 * 示例:
 * [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * 输出: [1,2,3]
 * <p>
 * 中序遍历
 * 访问顺序 左->根->右
 * <p>
 * 1-递归
 * 2-非递归 使用栈数据结构
 *
 * @author conceit
 * @since 1.0.0, 2019/7/23
 */
@SuppressWarnings("all")
public class BinaryTreeInorderTraversal {

	public static void main(String[] args) {

	}


	/**
	 * 中序遍历-迭代
	 * 中序遍历 需要借助 栈 数据结构
	 * 左->根->右
	 *
	 * 先获取到从root到左子孙节点入栈 这样每个左结点的上一个栈元素就是它的父节点
	 * 从栈顶开始出栈（既最左的子孙节点）
	 *
	 *
	 * 记录节点值
	 * 该节点的右节点
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> preOrderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (Objects.isNull(root)) {
			return result;
		}
		Stack<TreeNode> stack = new Stack<>();

		//当前计算的节点
		TreeNode cur=root;

		while (!stack.empty()||Objects.nonNull(cur)){
			//1- 第一次运行  从跟节点开始-到最左子孙节点依次入栈
			//每个栈元素的上级为自己的父节点
			//如果 该节点 依然有 右节点（右节点是其他节点的父节点。。。。），将该节点按照root节点处理
			//有点绕
			while (Objects.nonNull(cur)){
				stack.push(cur);
				//寻找最左子孙节点
				cur=cur.left;
			}
			//
			cur=stack.pop();
			result.add(cur.val);
			cur=cur.right;
		}


		return result;
	}

	/**
	 * 中序遍历-递归
	 * 左结点开始
	 * 左结点完成，加入root节点
	 * 右节点开始遍历
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> inOrderRecursion(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		inOrderRecursionHelper(root,result);
		return result;
	}

	public void inOrderRecursionHelper(TreeNode root, List<Integer> result) {
		if(Objects.nonNull(root)){
			inOrderRecursionHelper(root.left, result);
			result.add(root.val);
			inOrderRecursionHelper(root.right, result);
		}
	}


	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) {
			val = x;
		}
	}


}
